\documentclass[11pt, fleqn]{article}
\usepackage{amsmath}
\usepackage{amsfonts}

\begin{document}


\title{Assignment 2}
\author{James Gregory(3288801) \and Huy Nguyen(3430069) }
\date{\today}
\maketitle

\section*{Deliverables}
\subsection*{Promela}
Under the directory promela is our promela simulation of the pub-crawl. The 3 runtime parameters N, b and p are defined in the file \textbf{params.h}. In the file \textbf{pub.h} are several important flags:
\begin{itemize}
\item \textbf{smartDelegate:} Defines which algorithm for the delegates to be used (named smart or dumb).
\item\textbf{smartGuard:} Defines which algorithm for the bodyguards to be used (named smart or dumb).
\item \textbf{accumulativeCounting:} Enable or disable accumulative counting.
\item \textbf{debug:} Enable or disable extra printf information for debugging.
\end{itemize}
These individual algorithms are explained under the Algorithms section.

Included in this directory is also a shell script \textbf{test.sh}. The shell script takes the 3 parameters (N, p and b) as command line arguments as well as the number of times the simulation is run. Individual simulation output is hidden when running the script. The simulation can also be run individually to observe output from each round. The file \textbf{main.h} contains several flags such as debug for more output.

A bodyguard delegate pair is grouped in the same process "delegate". Each delegate process has their own channel from which they receive messages. A second channel "driverChannel" is used to communicated with the "designatedDriver" process. This driver maintains the flow of the simulation as well as checks for winning conditions. The driver communicated no information with the processes, other than opening or closing barriers, or informing the processes that a termination condition has been met.

\subsection*{MPI}

Under the directory \textbf{mpi} is the MPI implementation of the pub-crawl using MPI and the appropriate makefile. The MPI implementation produces output comparable to our promela implementation and uses algorithms similar to the smart delegates and bodyguards.

The solution introduces the game master, the equivalent of the driver in the promela implementation. The game master initiates and randomises the pub list and communicate with the delegates processors to check for winning game conditions. The game master processor is created dynamically independent of the arguments supplied at the command-line. The game master will always be processor 0. The application will also spawn more delegate processors, if the number of processors provided to mpirun is less than the N argument.

In the MPI solution, each delegate and their bodyguard are identified by a processor number, within a delegate group. This group and its communication channel are created to facilitate message exchange between delegates regarding votes and nominations. However, all the processors (including the game master) are in the world group and communicate on the world channel. Having separate channels and group removes the dirty complexity of filtering out the game master in the algorithm. We can also use the broadcast and gather functionalities of MPI which make code cleaner.

Each delegate's pub share the same number as delegate identifier. Thus, delegate 1 would have a local pub with id of 1. Furthermore, to differentiate between delegate and bodyguard, bodyguard id be offset by 1000. Thus, delegate 1 will have a bodyguard with id of 1001. For simplicity, we also differentiate between delegates' messages and bodyguards' messages by the message order. Each message will have two components: the first would be public delegates' messages whilst the second will contain bodyguards' secret messages.

Outputs of the MPI solutions are similar to the promela solutions, albeit more verbose.

\section*{The Problem}
\subsection*{Consensus and Byzantine Faults}
The pub and beer wench elections are examples of a consensus problem, multiple processes sharing information and then attempting to individually all come the the same conclusion. When the information gathered by individual process is the same, consensus is trivial. Any reasonable function, such as taking a majority would do. This equal spread of information is threatened in two cases, when  a process crashes unexpectedly (e.g. after sending their vote to only some delegates) or when a process fails in arbitrary ways (e.g. sending different votes to different delegates). These are known as crash faults and byzantine faults respectively. There are several methods for dealing with crash faults (timeouts, heartbeats, etc). For this assignment we assume the absence of crash faults. However we face byzantine faults in the form of intoxicated delegates and their subversive bodyguards.

\subsection*{Fault Tolerance}
There is much literature discussing different methods of dealing with byzantine faults but it is generally agreed that if enough nodes/processes are faulty then reliable consensus is impossible. For example, Lamport's paper "The Byzantine Generals Problem" explains that any solution using only "oral messages" (messages completely under the control of the sender, as we have in our assignment) can not reliably come to consensus. If one third or more of the processes are faulty, then reliability is impossible (Lamport et al., 1982). While our problem is different to the Byzantine Generals Problem, it does share this impossibility result.

\subsection*{Reliability}
The only case where there is absolute reliability is when the delegates never get intoxicated ($p\ge n$). As a result we must rely upon probabilistic reliability to asses our algorithms. Probabilistic reliability of one algorithm is of no use without any comparisons or baselines, which is our reason for including both "dumb" and "smart" algorithms for the delegates and bodyguards in our promela simulations.

\subsection*{Assumptions}
These are the following assumptions we have made from the specification:
\begin{itemize}
\item Both voting rounds only ever contain two nominations. These nominations are known by all delegate/bodyguard pairs.
\item Intoxicated delegates make it to the correct pub before the next round of voting.
\item If all the delegates get intoxicated they will eventually win (via previous assumption).
\item Body guards can not hijack the wench elections by nominating two subversive bodyguards and neither electing themselves as a beer wench. 
\item Bodyguards are not aware of the strategies employed by the delegates and vice versa. Byzantine faults are by definition systems failing in arbitrary ways. Thus it would seem "against the grain" of this assignment to implement an attempt to deal with byzantine faults by combatting a specific behaviour of that fault. On the other hand, this is fairly difficult to do as we are writing both the bodyguards and the delegates. This is addressed later under Limitations. 
\end{itemize}

\section*{Algorithms}
\subsection*{Dumb Delegates}
Our baseline algorithm for delegates is very simple. For both the pub and wench votes they use a coin flip to decide on their individual votes, and a one round majority to reach consensus. The local delegate randomly nominates the two beer wench nominees.
\subsection*{Dumb Bodyguards}
Dumb bodyguards represent byzantine faults without malicious intent. They are not attempting to split delegates or sabotage elections, but sending out their individual votes at random. That is essentially flipping a coin before sending out each vote, as opposed to before each round or adhering to some strategy.
\subsection*{Smart Delegates}
Algorithms attempting to provide fault tolerance for the Byzantine Generals problem previously mentioned, not only fail to be reliable with too many "traitors", but the number of messages to be exchanges also grows quickly (e.g. Kings algorithm with exponential growth). Our delegates pub voting algorithm is as follows:
\begin{enumerate}
\item Use coin flip to decide vote.
\item Send vote to all delegates.
\item Receive vote from all delegates.
\item Ignore votes of those we believe to be intoxicated.
\item Take majority.
\end{enumerate}
The only difference here from the dumb delegates is ignoring those we believe to be intoxicated. The beer wench elections provide the delegates with the unique ability (with regards to the Byzantine Generals problem) to potentially discover intoxicated candidates. This is done by deciding on a strategy agreed upon by all delegates. For the beer wench nominations (assuming delegates with id's 0 .. N):
\begin{enumerate}
\item Nominate delegate 0
\item Nominate bodyguard 0
\end{enumerate}
And for the actual elections (between wenchA and wenchB):
\begin{enumerate}
\item if ( isGuard (wenchA) $\wedge$ isDelegate(wenchB) ) $\rightarrow$ choose wenchA
\item if ( isGuard (wenchB) $\wedge$ isDelegate(wenchA) ) $\rightarrow$ choose wenchB
\item else choose MIN ( id (wenchA) , id (wenchB) )
\end{enumerate}
This has two main results, all sober delegates nominate the same two people, and all sober delegates come to the same vote. So if a different nomination is made, all delegates can infer that the local delegate is intoxicated. If a delegate receives a vote from another delegate that is different, the delegate receiving the vote can infer the delegate that sent it is intoxicated. It is important to note that no sober delegates are mistaken to be intoxicated (in theory).

When a delegate decides if he was elected to be a beer wench he does not actually use the votes he received. If the bodyguard of a sober delegate is nominated, the delegate pretends his bodyguard won the election (except in the case of two bodyguards where only one delegate does this). If both of the nominations are delegates, then the first delegate becomes the beer wench.

\subsection*{Smart Bodyguards}
Smart body guards represent byzantine faults with malicious intent. They actively attempt to split the delegates. In pub elections they collude to all send the same vote to one delegate whilst all sending a different vote to another delegate. By doing so they maximise their chances to sway the majority. When a bodyguard gets to nominate beer wenches they attempt to elect sober delegates in order to try to split them up. When bodyguards of intoxicated delegates are nominated for to be elected beer wench, they communicate with each other such that the bodyguard with the lowest drink count becomes the beer wench. If an intoxicated delegate is nominated as a beer wench the bodyguard will pretend that his delegate one the election.

\subsection*{Accumulative Counting}
This idea actually spawned from a mistake, forgetting to reset the vote counters when deciding on which pub to visit. However, it turns that doing so can increase the chances of delegates making a successful pub crawl. In theory, if the threshold of delegates is high, when they reach the $p$th pub they would all have the same total number of votes for options $A$ and $B$. If the difference between $A$ and $B$ is larger than $N$, the delegates will all agree on the next pub, if larger than $2*N$, they will make it to the two next pubs, and so on. The reason we did not leave this implemented as in some cases it may not comply with the spec, namely that delegates can only go to a pub that at least someone voted for. However as we this improvement from a mistake, and were not attempting to exploit any holes in the specification, we left it in as an option. 

\subsection*{Complexities and Limitations}

The complexity of our algorithm for delegates reaching consensus is linear with respect to the number of delegates (N) in time, space and communication. I am aware of improvements more complicated consensus algorithms can obtain for small numbers of faulty processes, such as the King's algorithm discussed in lectures which has an exponential complexity and has an upper bound of $N/3$ faulty processes. However I feel such increases in complexity in time, space, communication and implementation where there is a $50\%$ chance for $N/2$ delegates to become intoxicated in the $(p+1)th$ round.

Improvements in reaching consensus in the pub vote rely on detecting intoxicated delegates during the wench vote round. As a result their exists a tradeoff between subversive bodyguards attempting to sabotage the pub vote and the wench vote. If subversive body guards wish to remain undetected for the pub vote, they must "behave" like a sober delegate during the wench vote. 

\section*{Results}

Obviously there is a vast number of options for different run time parameters. For the purposes of this testing we chose $N = 7$, $p = 4$ and $b = 3$. We have no special reasons for choosing these numbers except that both bodyguards and delegates have are able to win.

\subsection*{Dumb Delegates and Dumb Bodyguards}
\subsection*{Smart vs. Dumb}
\subsection*{Dumb vs. Smart}
\subsection*{Smart vs. Smart}

\pagebreak
\section*{References}
Lamport, Leslie, Robert Shostak, and Marshall Pease. "The Byzantine generals problem." ACM Transactions on Programming Languages and Systems (TOPLAS) 4.3 (1982): 382-401.

\end{document}